\input{euler.tex}

\begin{document}

\problem[323]{Bitwise-OR Operations on Random Integers}

Let $\{y_0, y_1, y_2, \ldots\}$ be a sequence of independent, uniformly distributed random unsigned 32-bit integers (i.e. $0 \le y_i < 2^{32}$, every value equally likely).

Define the sequence $\{x_0, x_1, x_2, \ldots \}$ by the following recurrence relation:
\begin{align}
x_0 &= 0 \notag \\
x_i &= x_{i-1} \, | \, y_{i-1},  \, i > 0 \notag
\end{align}
where $|$ is the bitwise-OR operator.

It can be seen that eventually there will be an index $N$ such that $x_i = 2^{32} -1$ (a bit-pattern of all ones) for all $i \ge N$.

Find the expected value of $N$. Give your answer rounded to 10 digits after the decimal point.

\solution

Think of a 32-bit integer as an array of 32 lights which operate independently. In each ``turn-on-the-lights'' operation, (corresponding to the next element in the sequence $\{x_i\}$), each light that is off has $1/2$ probability of being turned on, and each light that is on remains on. Let $y_k$ denote the number of lights that are on after one operation on a group of $k$ lights that are initially off. It is easy to see that $y_k$ follows the binomial distribution, i.e.
\[
P(y_k = i) = \frac{C_k^i}{2^k}
\]
for $0 \le i \le k$.

Let $N(k)$ denote the expected number of operations needed to turn on exactly $k$ lights which are initially off. $N(0) = 0$. For $k > 0$, we have
\begin{align}
N(k) &= 1 + \sum_{i=0}^k P(y_k = i) N(k-i) \notag \\
&= 1 + \sum_{i=0}^k \frac{C_k^i}{2^k} N(k-i) \notag \\
&= 1 + \frac{1}{2^k} \left[ \sum_{i=1}^{k-1} C_k^i N(i) + N(k) \right] , \notag
\end{align}
which yields
\[
N(k) = 1 + \frac{1 + \sum_{i=1}^{k-1} C_k^i N(i)}{2^k-1} .
\]
The answer to the problem is just $N(32)$.

\complexity

Let $n$ be the number of bits in the integer.

Time complexity: $\BigO(n^2)$.

Space complexity: $\BigO(n)$.

\answer

6.3551758451

\end{document} 